package com.sheng.leetcode.year2022.swordfingeroffer.day18;

import org.junit.Test;

import java.util.LinkedList;

/**
 * @author liusheng
 * @date 2022/09/16
 *<p>
 * 剑指 Offer 55 - I. 二叉树的深度<p>
 * <p>
 * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。<p>
 *<p>
 * 例如：<p>
 *<p>
 * 给定二叉树 [3,9,20,null,null,15,7]，<p>
 *<p>
 *     3<p>
 *    / \<p>
 *   9  20<p>
 *     /  \<p>
 *    15   7<p>
 * 返回它的最大深度3 。<p>
 *<p>
 * 提示：<p>
 *<p>
 * 节点总数 <= 10000<p>
 * 注意：本题与主站 104题相同：<a href="https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0055 {

    @Test
    public void test01() {
        TreeNode root = new TreeNode(3);
        TreeNode right = new TreeNode(20);
        right.left = new TreeNode(15);
        right.right = new TreeNode(7);
        root.left = new TreeNode(9);
        root.right = right;
        System.out.println(new Solution().maxDepth(root));
    }
}
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // bfs
        int depth = 0;
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (!list.isEmpty()) {
            // 深度加1
            depth++;
            // 获取集合中的元素总数
            int size = list.size();
            // 依次取出，并判断是否有子树
            for (int i = 0; i < size; i++) {
                TreeNode pop = list.pop();
                if (pop.left != null) {
                    list.add(pop.left);
                }
                if (pop.right != null) {
                    list.add(pop.right);
                }
            }
        }
        return depth;
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
